package leetcode_day._2022._202209._2130;

/**
 * 707. 设计链表
 * 算法：链表
 *
 * @author yzh
 * @version 1.0
 * @date 2022/9/24 14:50
 */
public class _23_707 {

    class MyLinkedList {

        class Node {
            int val;
            Node prev;
            Node next;

            public Node(int val) {
                this.val = val;
            }

        }

        int sz = 0;
        Node he = new Node(-1), ta = new Node(-1);

        public MyLinkedList() {
            he.next = ta;
            ta.prev = he;
        }

        public int get(int index) {
            Node node = getNode(index);
            return node == null ? -1 : node.val;
        }

        public void addAtHead(int val) {
            Node node = new Node(val);
            node.prev = he;
            node.next = he.next;
            he.next.prev = node;
            he.next = node;
            ++sz;
        }

        public void addAtTail(int val) {
            Node node = new Node(val);
            node.prev = ta.prev;
            node.next = ta;
            ta.prev.next = node;
            ta.prev = node;
            ++sz;
        }

        public void addAtIndex(int index, int val) {
            if (index > sz) return;
            if (index <= 0) addAtHead(val);
            else if (index == sz) addAtTail(val);
            else {
                Node cur = getNode(index), node = new Node(val);
                node.prev = cur.prev;
                node.next = cur;
                cur.prev.next = node;
                cur.prev = node;
                ++sz;
            }
        }

        public void deleteAtIndex(int index) {
            Node node = getNode(index);
            if (node == null) return;
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
            --sz;
        }

        public Node getNode(int index) {
            boolean isLeft = index < sz / 2;
            if (!isLeft) index = sz - index - 1;
            for (Node node = isLeft ? he.next : ta.prev; node != he && node != ta; node = isLeft ? node.next : node.prev)
                if (index-- == 0) return node;
            return null;
        }

    }

}
